package com.example.demo.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.cn/problems/subarray-sum-equals-k/?envType=study-plan-v2&envId=top-100-liked
 *
 * @author WangYX
 * @version 1.0.0
 * @date 2024/03/01 11:24
 */
public class _560_和为K的子数组 {

    public static void main(String[] args) {
        int[] nums = {1, 1, 1};
        int k = 2;


        int[] nums1 = {1, 2, 3};
        int k1 = 3;
        int i = subarraySum1(nums, k);
        System.out.println(i);
    }

    /**
     * 前缀和+ 哈希
     *
     * @param nums
     * @param k
     * @return {@link int}
     * @author WangYX
     * @date 2024/03/01 11:47
     */
    public static int subarraySum(int[] nums, int k) {
        if (nums.length == 1) {
            if (nums[0] == k) {
                return 1;
            } else {
                return 0;
            }
        }
        int[] sums = new int[nums.length];
        Map<Integer, Integer> map = new HashMap<>(nums.length);
        map.put(0, 0);
        int num = 0;
        for (int i = 1; i <= nums.length; i++) {
            int sum = nums[i - 1];
            if (i - 2 >= 0) {
                sum += sums[i - 2];
            }
            sums[i - 1] = sum;
            map.put(sum, i);
            if (map.get(sum - k) != null) {
                num++;
            }
        }
        return num;
    }

    public static int subarraySum1(int[] nums, int k) {
        int count = 0, pre = 0;
        HashMap < Integer, Integer > mp = new HashMap < > ();
        mp.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            if (mp.containsKey(pre - k)) {
                count += mp.get(pre - k);
            }
            mp.put(pre, mp.getOrDefault(pre, 0) + 1);
        }
        return count;
    }
}
